/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

/**
 * @author : sunzb
 * @date: 2019/5/15
 */
public class _27_338_CountingBits {

    public static int[] countBits1(int num) {
        int[] res = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            res[i] = res[i & i - 1] + 1;
            System.out.println(String.format("i:[%s],i&i-1:[%s],res[i]:%s", i, i & i - 1, res[i]));
        }
        return res;
    }

    public static int[] countBits(int num) {
        int[] res = new int[num + 1];
        for (int i = 0; i <= num; i++)
            res[i] = hammingWeight(i);
        return res;
    }

    public static int hammingWeight(int n) {
        int count = 0;
        for (; n != 0 ; n = n & n - 1) count++;
        return count;
    }

    public static void main(String[] args) {
        countBits1(10);
    }
}
